import java.util.*;


/**
 * Represents a genetic utilities library with different operators
 * @author matan
 *
 */
public class GeneticUtils {
	
	//Constants
	public static final double CROSSOVER = 0.8;		///< Crossover rate
	public static final double MUTATION = 0.05;		///< Mutation rate
	public static final int GENERATIONS = 5000;		///< Number of generations
	public static final int POPULATION = 100;		///< Population size
	public static int NUM_COLORS ;				///< Number of colors
	public static int ELITISM = 6;					///< Number of best clones
	public static final double WEIGHT = 0.7;
	public static double PENALTY = 0;
	
	//Data members
	private int _length; ///< Chromosome's length
	private static InputData _input = null;
	private int maxError = 0;
	
	//Random generator
	public static Random rnd = new Random(System.currentTimeMillis());
	
	/**
	 * Constructor
	 * @param length Chromosome length
	 */
	public GeneticUtils(int length, InputData input, int numColors) {
		_length = length;
		NUM_COLORS = numColors;
		_input = input;
		
		// calculate max error
		maxError = 0;
		for (int i = 0; i < length; ++i) {
			if (input.getNeighbors(i) != null)
				maxError += input.getNeighbors(i).size();
		}
	}
	
	/**
	 * Mutation operator: scans all chromosome's data elements and randomly mutates them
	 * @param c chromosome
	 * @return mutated chromosome
	 */
	public Chromosome mutate(Chromosome c) {
		int ind1, ind2;
		ind1 = GeneticUtils.rnd.nextInt(_length);
		ind2 = GeneticUtils.rnd.nextInt(_length);
		
		int tempColor = c.getData(ind1);
		c.setData(ind1, c.getData(ind2));
		c.setData(ind2, tempColor);
		
		return c;
	}

	/**
	 * get the number of errors in the chromosome
	 * @param c - the chromosome to evaluate
	 * @return the number or edges that the 2 nodes has the same color
	 */
	public static int getErrors(Chromosome c) {
		List<Integer> coloring = c.getAll();
		
		int errors = 0;
		for (int i = 0; i < coloring.size(); ++i) {
			List<Integer> neighbors = _input.getNeighbors(i);
			
			if (neighbors == null)
				continue;
			
			int currColor = coloring.get(i);
			
			for (int j = 0; j < neighbors.size(); ++j) {
								
				if (coloring.get(neighbors.get(j)) == currColor)
					++errors;
			}
		}
		return errors / 2;
	}

	/**
	 * @param c chromosome to be evaluated
	 * @return fitness of given chromosome
	 */
	public double fitness1(Chromosome c) {
		List<Integer> coloring = c.getAll();
		int count4Color = 0;
		
		int fitnessValue = 0;
		for (int i = 0; i < coloring.size(); ++i) {
			List<Integer> neighbors = _input.getNeighbors(i);
			
			if (neighbors == null)
				continue;
			
			int currColor = coloring.get(i);
			if (currColor == 3)
				++count4Color;
			
			for (int j = 0; j < neighbors.size(); ++j) {
								
				if (coloring.get(neighbors.get(j)) != currColor)
					fitnessValue += 1;
			}
		}
		return Math.max(0,fitnessValue - count4Color*PENALTY);
	}
	
	/**
	 * Breeds 2 chromosomes
	 * @param father first chromosome to be breed
	 * @param mother second chromosome to be breed
	 * @return list of offsprings
	 */
	public List<Chromosome> breed(Chromosome father, Chromosome mother) {
		List<Chromosome> offsprings = new LinkedList<Chromosome>();
		
		if (rnd.nextDouble() > CROSSOVER) {
			
			Chromosome clonedFather = father.clone();
			mutate(clonedFather);
			clonedFather.setFitness(fitness1(clonedFather));
			
			Chromosome clonedMother = mother.clone();
			mutate(clonedMother);
			clonedMother.setFitness(fitness1(clonedMother));
			
			if (rnd.nextDouble()>0.5)
				offsprings.add(clonedFather);
			else
				offsprings.add(clonedMother);
			
			return offsprings;
		}
		
		//Choose random crossover index
        int crossoverIndex = rnd.nextInt( _length);
        List<Integer> fatherVal, motherVal;
        Chromosome big=null,small=null;
        big = father.getFitness()>mother.getFitness() ? father : mother;
        small = father.getFitness()>mother.getFitness() ? mother : father;
        
        List<Integer> newGene = new LinkedList<Integer>();
        for (int i=0;i<father.getLength();++i)
        {
        	if (rnd.nextDouble() > WEIGHT)
        		newGene.add(small.getData(i));
        	else
        		newGene.add(big.getData(i));
        }
        
        Chromosome firstOffspring = new Chromosome(newGene);
     
        //Mutate new siblings
        mutate(firstOffspring);
        
        //Calculate fitness of new siblings
        firstOffspring.setFitness(fitness1(firstOffspring));
        
        offsprings.add(firstOffspring);
        
		return offsprings;
	}
	
	public int getMaxError() {
		return maxError;
	}
}